/**
 * 使用dfs实现优先无环图的拓扑排序
 * 
 * 在dfs的基础上加上time变量（记录节点的结束时间）
 * 将结束时间从小到大排序，即可得到拓扑排序
 */
#include"store_matrix.h"

//标记i节点是否访问
bool visited[MaxVertexNum];
//访问一个节点
void visit(int v){}

int time=0;

void dfsTraverse(MGraph *g){
    for(int v=0;v<g->vernum;v++){
        visited[v]=false;//初始化访问标记数组
    }
    //开始深度遍历
    for(int v=0;v<g->vernum;v++){
        if(!visited[v]) dfs(g,v);
    }
}
//记录每个节点的完毕时间
int finishTime[MaxVertexNum];
//深度遍历
void dfs(MGraph *g,int v){
    //先标记访问这个节点，然后访问
    visited[v]=true;
    visit(v);
    //访问完毕后。找到当前节点的下一个节点，然后访问，递归dfs
    for(w=firstNeighbor(g,v);w>=0;w.nextNeighbor(g,v,w)){
        if(!visited[w]){
            dfs(g,w);
        }
    }
    time=time+1;
    finishTime[v]=time;
}